# 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
#
# 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
#
# 示例 1:
# 输入：nums = [1,2,3]
# 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
# 示例 2:
# 输入：nums = [0]
# 输出：[[],[0]]
from typing import List


class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = list[List[int]]()

        def findSubsets(nums: List[int], index: int, current_subset: List[int]) -> None:
            if index == len(nums):
                res.append(current_subset[:])  # 需要 copy 一下，不然后面的操作会导致这个对象被清空
                # res.append(current_subset) # 需要 copy 一下，不然后面的操作会导致这个对象被清空
                return
            # 不选择当前元素，递归到下一个元素是否选择(此时不需要还原现场，因为没选当前元素)
            findSubsets(nums, index + 1, current_subset)

            # 选择当前元素，然后递归到下一个元素是否选择
            current_subset.append(nums[index])
            findSubsets(nums, index + 1, current_subset)
            # 还原临时结果集的现场
            current_subset.pop()

        findSubsets(nums, 0, [])
        return res


if __name__ == "__main__":
    nums = [1, 2, 3]
    nums = [0, 1]
    print(Solution().subsets(nums))
